package com.lin.linojcodesandbox.leetcode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class Main {
    /**
     * 3、无重复字符的最长字串  pwwkew
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring(String s) {
        if(s.length()==0)
            return 0;
        int i=0;
        int j=1;
        int sum = 1;
        int max = 1;
        Map<Character,Integer> map = new HashMap<>();
        map.put(s.charAt(0),1);
        while(i<=j && j<s.length()){
            char c = s.charAt(j);
            if(!map.containsKey(c) || map.get(c)==0){
                sum++;
                map.put(c,1);
                max = Math.max(sum,max);
                j++;
                continue;
            }

            while(i<=j){
                if(s.charAt(i)!=c){
                    map.put(s.charAt(i),0);
                    i++;
                    sum--;
                }else{
                    break;
                }
            }
            i++;
            j++;
        }
        return max;
    }

    /**
     * 1004、最大连续1的个数III
     * @param nums
     * @param k
     * @return
     */
    public static int longestOnes(int[] nums, int k) {
        int i = 0;
        int j = 0;
        int max = 0;
        // 记录数组中出现0的位置
        Queue<Integer> queue = new LinkedList<>();
        while(i<=j && j< nums.length){
            if(nums[j]==1){
                j++;
                max = Math.max(max,j-i);
                continue;
            }
            if(nums[j]==0 && k>0){
                queue.offer(j);
                k--;
                j++;
                max = Math.max(max,j-i);
            }else{
                if(!queue.isEmpty()){
                    i = queue.poll()+1;
                    k++;
                }else{
                    j++;
                    i = j;
                }
            }
        }

        return max;
    }


    /**
     * 1208、尽可能使字符串相等
     * @param s
     * @param t
     * @param maxCost
     * @return
     */
    public static int equalSubstring(String s, String t, int maxCost) {
        int max = 0;
        for(int start = 0,end =0;end<s.length();++end){
            int val = Math.abs(s.charAt(end) - t.charAt(end));
            if(val<=maxCost){
                maxCost -= val;
                max = Math.max(max,end-start+1);
                continue;
            }
            while(val>maxCost){
                maxCost += Math.abs(s.charAt(start) - t.charAt(start));
                start++;
            }
            end--;
        }
        return max;
    }

    public static void main(String[] args) {
//        lengthOfLongestSubstring("bbbbb");
//        int[] nums = {0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1};
//        longestOnes(nums,3);
        equalSubstring("abcd","cdef",0);
    }
}
